#include "prefix-tree.h"
#include "../draw.h"

#define RAYON 7

//-----------------------------------------------------------------------------
ptree_t * PTree_getNode(ptree_t * node, byte b)
//-----------------------------------------------------------------------------
{
	//TODO peut-on optimiser en faissant remonter en tête les noeuds les plus fréquement consultés ?
	ptree_t * child = node->firstchild;

	while(child)
	{
		if(child->c == b) break;
		child = child->right;
	}

	return child;
}


//-----------------------------------------------------------------------------
int PTree_readWord(ptree_t * node, byte * word)
//-----------------------------------------------------------------------------
{
	ptree_t * n = node;
	int wordlen=0;
	int i,j;
	byte tmp;

	while(n && n->up)	//tanque racine non atteinte
	{
		word[wordlen]=n->c;
		wordlen++;
		n = n->up;
	}//lorsque n = racine n->c = ε

	//inverser le mot
	i=0;
	j=wordlen-1;
	while(i<j) {tmp=word[i]; word[i]=word[j]; word[j]=tmp; i++; j--;}

	return wordlen;
}


//-----------------------------------------------------------------------------
void PTree_cat(ptree_t * prefix, ptree_t * sufix)
//-----------------------------------------------------------------------------
{
	//insertion en tête de liste
	ptree_t * tmp =	prefix->firstchild;
	prefix->firstchild = sufix;
	sufix->right = tmp;

	sufix->up = prefix;
}
//-------------------------------------------------------------------------------
static void draw_recursif(ptree_t *arbre, int gauche, int droite, int hauteur)
//-------------------------------------------------------------------------------
{
	if (arbre)
	{
		vec2_t	v={ (droite-(droite-gauche)/2), hauteur };
		cir_t	noeud={ {(droite-(droite-gauche)/2), hauteur} , RAYON };

		char buf[2];
		DrawCir(& noeud);
		buf[0]=arbre->c, buf[1]= '\0';
		DrawText(v,buf);

		int count=0;
		ptree_t * temp;
		if (arbre->firstchild)
		{
			temp=arbre->firstchild;
			while (temp)
			{
				count++;
				temp=temp->right;
			}

			temp=arbre->firstchild;

			int i,newgauche,newdroite;
			for (i=0; i<count;i++)
			{
				newgauche=gauche+i*(droite-gauche)/count;
				newdroite=gauche+(i+1)*(droite-gauche)/count;
				draw_recursif(temp, newgauche, newdroite, hauteur-25);
				cir_t sous_noeud={ {newgauche+(newdroite-newgauche)/2,hauteur-25}, RAYON};
				DrawLink(& noeud,& sous_noeud);
				temp=temp->right;
				//(2*i+1)*(gauche+(i+1)*(droite-gauche)/count-(gauche+(i+1)*(droite-gauche)/count-gauche+i*(droite-gauche)/count)/2)
			}
		}

	}


}

//---------------------------------------------------------------------------
void PTree_draw(ptree_t * arbre, char * filename)
//---------------------------------------------------------------------------
//Dessine un arbre sur un fichier filename a partir de son sommet de type ptree_t
{
	FILE * f=NULL;
	if ( (f=fopen(filename,"wb")) )
	{

		PS_option_t options;
		options.fd = f;
		options.h = 300;
		options.w = 500;

		InitDraw((void*) &options);


		draw_recursif(arbre,0,500, 285);


		fclose(f);
	}
	else perror("PTree_draw()");
}



/*
//--------------- tests de la stucture----------------------

void init(ptree_t * p){ //initialisation d'un noeud

	p->up=NULL;
	p->firstchild=NULL;
	p->right=NULL;
	p->c='\0';
	p->id=0;
}

void afficherNoeud(ptree_t * p)
{
	ptree_t * n;
	printf("noeud: %c\n",p->c);
	if(p->up) printf("père = %c\n",p->up->c);
	else	  printf("père = NULL\n");
	if(p->right)	printf("frère = %c\n",p->right->c);
	else			printf("frère = NULL\n");
	if(p->firstchild)
	{
		printf("fils = ");
		n=p->firstchild;
		while(n)
		{
			printf("%c ",n->c);
			n= n->right;
		}
		printf("\n");
	}else printf("fils = NULL\n");

}

void afficherdico(ptree_t * p){

	byte word[20];
	int len=0;

	if(p != NULL)
	{
		len=PTree_readWord(p,word); word[len]='\0';
		printf("%s (%d)\n", word, len);

		if (p-> firstchild) {afficherdico(p->firstchild);}

		if (p->right) {afficherdico(p->right);
		}
	}
}


//------------------------------------------------------------------------------
int main()
//---------------------------------------------------------------------------
{
	ptree_t p1, p2, p3, p4, p5, p6,p7,p8,p9, p10, * n;
	init(& p1); init(& p2); init(& p3); init(& p4); init(& p5); init(& p6); init(& p7); init(& p8); init(& p9); init(& p10);
	p1.c = '0'; p1.id = 0;
	p2.c = 'a'; p2.id = 1;
	p3.c = 'b'; p3.id = 2;
	p4.c = 'c'; p4.id = 3;
	p5.c = 'd'; p5.id = 4;
	p6.c = 'e'; p6.id = 5;
	p7.c = 'f'; p7.id = 6;
	p8.c = 'g'; p8.id = 7;
	p9.c = 'h'; p9.id = 8;
	p10.c= 'i'; p10.id = 9;


	PTree_cat(& p1, &p4);
	PTree_cat(& p1, &p3);
	PTree_cat(& p1, &p2);

	PTree_cat(& p3, &p5);
	PTree_cat(& p4, &p6);
	PTree_cat(& p5, &p7);
	PTree_cat(& p5, &p8);
	PTree_cat(& p6, &p9);

	PTree_cat(& p5, &p10);

	afficherdico(&p1);

	n = &p1;

	afficherNoeud(n);
	n = PTree_getNode(n,'c');
	afficherNoeud(n);
	n = PTree_getNode(n,'e');
	afficherNoeud(n);
	n = PTree_getNode(n,'f');
	if(n)afficherNoeud(n);
	else printf("null\n");

	PTree_draw(& p1);


	return 0;
}
*/
